package primary.primary0;

/**
 * 动态规划
 */
public class S0198打家劫舍 {

    /**
     * 这是答案，答案的递归逻辑为:
     * 不管当前位置是否偷了，总之到了当前位置，最大值mi为，Math.max(前一个没偷 + nums[i], 前一个偷了)
     * 前一个没偷的最大值为 当前位置之前两个位置的最大值，也就是 m(i - 2)
     */
    public int rob(int[] nums) {
        int prev = 0;
        int curr = 0;

        // 每次循环，计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
        }

        return curr;
    }


    /**
     * 100，92
     * 当前偷了的和没偷的最大值，只和前一个相关
     */
    class Solution {
        public int rob(int[] nums) {
            int preStealed = 0;
            int preUnStealed = 0;

            int curStealed = 0;
            int curUnStealed = 0;

            for (int i = 0; i < nums.length; i++) {
                curStealed = preUnStealed + nums[i];
                // 注意这个，前一个可偷可不偷，不一定是投了
                curUnStealed = Math.max(preStealed, preUnStealed);

                preStealed = curStealed;
                preUnStealed = curUnStealed;
            }

            return Math.max(curStealed, curUnStealed);

        }
    }
}
